package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

/**
 * 拉格朗日插值多项式（含化简和霍纳法则优化）
 */
public class LagrangePolynomial {
    private final List<LagrangeItem> items;       // 原始拉格朗日项
    private final List<Double> polynomial;        // 化简后的多项式系数（霍纳形式）

    public LagrangePolynomial(List<LagrangeItem> items) {
        this.items = items;
        // 步骤1：化简每个拉格朗日项为多项式
        List<List<Double>> polynomials = new ArrayList<>();
        for (LagrangeItem item : items) {
            // 计算系数：y / 分母
            double coeff = item.getY() / item.getLagrangeFraction().getDenominator();
            // 构建一次多项式矩阵：[(1, -x1), (1, -x2), ...]
            List<List<Double>> matrix = new ArrayList<>();
            for (double numerator : item.getLagrangeFraction().getNumerators()) {
                matrix.add(List.of(1.0, -numerator));
            }
            // 将系数乘到第一个多项式上
            if (!matrix.isEmpty()) {
                List<Double> firstPoly = new ArrayList<>();
                firstPoly.add(matrix.get(0).get(0) * coeff);
                firstPoly.add(matrix.get(0).get(1) * coeff);
                matrix.set(0, firstPoly);
            }
            // 多项式展开化简
            List<Double> simplifiedPoly = PolynomialUtils.polynomialSimplify(matrix);
            polynomials.add(simplifiedPoly);
        }

        // 步骤2：合并所有多项式（同次项系数相加）
        int polySize = items.size(); // 多项式次数 = 项数 - 1，系数数组长度 = 项数
        this.polynomial = new ArrayList<>();
        for (int i = 0; i < polySize; i++) {
            this.polynomial.add(0.0);
        }

        for (List<Double> poly : polynomials) {
            for (int i = 0; i < poly.size(); i++) {
                // 确保索引不越界（低次项补0）
                if (i < this.polynomial.size()) {
                    double val = this.polynomial.get(i) + poly.get(i);
                    this.polynomial.set(i, val);
                }
            }
        }
    }

    /**
     * 霍纳法则求值（优化后的高效求值）
     * @param x 自变量值
     * @return 多项式值
     */
    public double apply(double x) {
        double result = 0.0;
        for (double coefficient : polynomial) {
            result = result * x + coefficient;
        }
        return result;
    }

    /**
     * 格式化输出原始拉格朗日多项式字符串
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (LagrangeItem item : items) {
            // 构建分子部分：(x - x1)(x - x2)...
            StringBuilder numeratorStr = new StringBuilder();
            for (double num : item.getLagrangeFraction().getNumerators()) {
                numeratorStr.append(String.format("(x-%s)", num));
            }
            // 构建单项字符串：(x-x1)(x-x2)*y/(分母)
            String itemStr = String.format("%s*%s/(%s)",
                    numeratorStr, item.getY(), item.getLagrangeFraction().getDenominator());

            if (!first) {
                sb.append("+");
            } else {
                first = false;
            }
            sb.append(itemStr);
        }
        return sb.toString();
    }

    // Getter方法
    public List<Double> getPolynomial() {
        return new ArrayList<>(polynomial);
    }

    public List<LagrangeItem> getItems() {
        return new ArrayList<>(items);
    }
}